package history

func getOutPoints(points [][2]float64) [][2]float64 {
	var left = points[0]
	var top = points[0]
	var right = points[0]
	var bootom = points[0]
	for i := 0; i < len(points); i++ {
		if points[i][0] < left[0] {
			left = points[i]
		}
		if points[i][1] > top[1] {
			top = points[i]
		}
		if points[i][0] > right[0] {
			right = points[i]
		}
		if points[i][1] < bootom[1] {
			bootom = points[i]
		}
	}
	var res [][2]float64
	var queue = [][2]float64{top, right, bootom}
	res = append(res, left)
	for len(queue) > 0 {
		var point2 = queue[0]
		var point1 = res[len(res)-1]
		if point1 != point2 {
			var rate = (point2[1] - point1[1]) / (point2[0] - point1[0])
			var maxRate = rate - 1.00
			var curResPoint [2]float64
			for i := 0; i < len(points); i++ {
				if points[i] != point1 {
					var curRate = (points[i][1] - point1[1]) / (points[i][0] - point1[0])
					if curRate > rate && curRate > maxRate {
						maxRate = curRate
						curResPoint = points[i]
					}
				}
			}
			// 计算在当前直线上的点，可能有多个，需要多次记录
			if maxRate == rate {
				res = append(res, curResPoint)
				res = append(res, point2)
				queue = queue[1:]
			} else if maxRate > rate {
				queue = append(queue, curResPoint)
			}
		}

	}
	return res
}
